package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/can-i-win/
 * @create 2025/9/12 17:45
 * @since JDK17
 */

public class Solution05 {
    int[] dp;
    int n;
    boolean f(int status, int rest) {
        if (rest <= 0) {    // 当前这个人输了
            return false;
        }
        if (dp[status] != 0) {
            return dp[status] == 1;
        }
        boolean ans = false;
        for (int i = 1; i <= n; i++) {  // n个选择
            if ((status ^ (1 << i)) != 0 && !f(status ^ (1 << i), rest - i)) {
                ans = true;
                break;
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }

    public boolean canIWin(int n, int rest) {
        if (rest == 0) {
            return true;
        }
        if ((1 + n) * n / 2 < rest) {
            return false;
        }
        dp = new int[1 << (n + 1)]; // 0 : 未使用， 1 : true, -1 : false
        this.n = n;
        return f(1 << (n + 1) - 1, rest);
    }
}
